import collections
import queue

from collections import deque


class OtherSolution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        
        def construct_dict(word_list):
            d = {}
            for word in word_list:
                for i in range(len(word)):
                    s = word[:i] + "_" + word[i + 1:]
                    d[s] = d.get(s, []) + [word]
            return d
        
        def bfs_words(begin, end, dict_words):
            queue, visited = deque([(begin, 1)]), set()
            while queue:
                word, steps = queue.popleft()
                if word not in visited:
                    visited.add(word)
                    if word == end:
                        return steps
                    for i in range(len(word)):
                        s = word[:i] + "_" + word[i + 1:]
                        neigh_words = dict_words.get(s, [])
                        for neigh in neigh_words:
                            if neigh not in visited:
                                queue.append((neigh, steps + 1))
            return 0
        
        if endWord not in wordList:
            return 0
        
        d = construct_dict(set(wordList) | set([beginWord, endWord]))
        return bfs_words(beginWord, endWord, d)


class Solution(object):
    def ladderLength(self, beginWord, endWord: list, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        wordList = dict(zip(wordList,[1]*len(wordList)))
        if endWord not in wordList:
            return 0
        char_table = []
        for j in range(26):
            char_table.append(chr(j + ord('a')))
        q = queue.Queue()
        word_dict = {}
        q.put(beginWord)
        word_dict[beginWord] = 1
        while not q.empty():
            word = q.get()
            print(word,end='->')
            level = word_dict[word]
            for i in range(len(word)):
                char_list = list(word)
                for char in char_table:
                    if char==char_list[i]:
                        continue
                    char_list[i] = char
                    check = ''.join(char_list)
                    if check == endWord:
                        print(endWord)
                        return word_dict[word] + 1
                    if wordList.get(check)==1 and word_dict.get(check)==None:
                        q.put(check)
                        word_dict[check] = level + 1
        return 0

def main():
    sol = OtherSolution()
    print(sol.ladderLength("qa","sq",["si","go","se","cm","so","ph","mt","db","mb","sb","kr","ln","tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn","ya","cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo","as","fr","nb","yb","if","pb","ge","th","pm","rb","sh","co","ga","li","ha","hz","no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la","st","er","sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he","lr","sq","ye"]))


if __name__ == "__main__":
    main()
